package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Scanner;

/**
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
 *
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 *
 * 示例：
 *
 * 输入：nums: [1,1,1,1,1], S: 3
 * 输出：5
 *
 * 解释：
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 *
 * 一共有5种方法让最终目标和为3。
 *
 * 提示：
 *
 * 数组非空，且长度不会超过 20 。
 * 初始的数组的和不会超过 1000 。
 * 保证返回的最终结果能被 32 位整数存下。
 */
// 假设加法的总和为x，那么减法对应的总和就是sum - x,所以我们要求的是 x - (sum - x) = S,x = (S + sum) / 2,此时问题就转化为，装满容量为x背包，有几种方法
// 再回归到01背包问题，为什么是01背包呢？因为每个物品（题目中的1）只用一次！
public class FindTargetSumWays {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String[] strings = scanner.nextLine().split(",");
            int S = scanner.nextInt();
            int[] nums = new int[strings.length];
            int sum = 0;
            for (int i = 0; i < strings.length; i++) {
                if (!strings[i].equals("")) {
                    nums[i] = Integer.parseInt(strings[i]);
                    sum += Integer.parseInt(strings[i]);
                }
            }
            if ((sum + S) % 2 != 0) {
                System.out.println(0);
            } else {
                int target = (sum + S) / 2;
                int[] dp = new int[target + 1];
                dp[0] = 1;
                for (int i = 0; i < nums.length; i ++) {
                    // 从后往前遍历的话nums里面的每个元素只使用一次
                    for (int j = target; j >= nums[i]; j --) {
                        dp[j] += dp[j - nums[i]];
                    }
                }
                System.out.println(dp[target]);
            }

        }

    }

}
